BZOJ 2818 & 2820 Gcd (欧拉函数/莫比乌斯反演)

Posted on | In , , , ,

给定一个$n$，问$\gcd(x,y)$为质数的对数
$n,m\le10^7,1\le x,y \le n$

欧拉函数解法

  • 考虑枚举每个质数g
  • 对于每个g，有多少对数(x,y)的gcd(x,y)=g，即为$\phi[\frac{n}{g}]$
  • 线性递推求欧拉函数即可，注意$\phi(1)设为0$，$x=y$且 $x$ 和 $y$ 为素数的情况只有一对满足
  • 前面的答案$×2$ 是最后的答案？
  • 漏掉了$x=y$且 $x$ 和 $y$ 为素数的情况，加上即可

莫比乌斯反演解法

若这个题$x，y$的数据范围不一样则必须用莫比乌斯反演了,比如BZOJ 2820(权限题)

  • 设$(n<m)$，不符合${\rm swap}(n,m)$即可
  • 设$n$以内的素数为$p$，一共有$N$个
  • $\sum _{isprime(p)}^{N}\sum _{i=1}^{n}\sum _{j=1}^{m}[\gcd(i,j)=p]$
  • $\sum _{isprime(p)}^{N}\sum _{i=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\sum _{j=1}^{\left \lfloor \frac{m}{p} \right \rfloor}[\gcd(i,j)=1]$
  • 莫比乌斯反演可得
  • $\sum _{isprime(p)}^{N}\sum _{i=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\sum _{j=1}^{\left \lfloor \frac{m}{p} \right \rfloor}\sum _{ d|\gcd(i,j)}\mu(d)$
  • $\sum _{isprime(p)}^{N}\sum _{i=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\sum _{j=1}^{\left \lfloor \frac{m}{p} \right \rfloor}\sum _{ d|i \wedge d|j }\mu(d)$
  • $\sum _{isprime(p)}^{N}\sum _{d=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\mu(d)\left \lfloor \frac{n}{pd} \right \rfloor \left \lfloor \frac{m}{pd} \right \rfloor$
  • 这样直接做的复杂度是$O(\frac{n}{logn}·\sqrt{n})$，显然无法通过此题
  • 令$pd=k$
  • $\sum _{k=1}^{n}\sum _{isprime(p)\wedge p|k}^{N}\mu(\frac{k}{p})\left \lfloor \frac{n}{k} \right \rfloor \left \lfloor \frac{m}{k} \right \rfloor$
  • 预处理所有k的系数即$\sum _{isprime(p)\wedge p|k}^{N}\mu(\frac{k}{p})$，具体方法：线性筛mobius，然后枚举质数及其倍数，求出每个系数
  • 后面就是整除分块了，但对于每一块要保证n和m的值都不会变才行，即$r=\min(n/(n/l),m/(m/l))$

莫比乌斯反演代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<cstdio>
#include<iostream>
using namespace std;
#define ll long long
const int N=1e7+100;

int isprime[N],mu[N],prime[N], tot; //isprime[i]:i是否为素数。mu[]:莫比乌斯函数。tot素数个数

ll ans, sum[N];
int n, m;


void Mobius(int n)
{
    int i,j;
    tot=0;mu[1]=1;
    for(i=2;i<=n;i++){
        if(!isprime[i]){
            prime[tot++]=i;
            mu[i]=-1;
        }
        for(j=0; j<tot && i*prime[j]<=n;j++){
            isprime[i*prime[j]]=1;
            if(i%prime[j])  mu[i*prime[j]]=-mu[i];
            else    {mu[i*prime[j]]=0;break;}
        }
    }
    for(int i=0;i<tot;i++)
    {
        for(int j=1;j*prime[i]<=n;j++)
            sum[j*prime[i]] += mu[j];
    }
    for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
}

ll solve()
{
    ans=0;
    if(n>m) swap(n,m);
    for(int l=1, r;l<=n;l=r+1)
    {
        r=min(n/(n/l), m/(m/l));
        //cout<<sum[r]<<endl;
        ans += 1LL*(n/l) * 1LL*(m/l) * 1LL*(sum[r]-sum[l-1]);
    }
    return ans;
}

int main()
{
    Mobius(N-100+2);
    scanf("%d%d", &n, &m);
    solve();
    printf("%lld\n", ans);
}